\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{Bellman-Ford算法的实现}


 \author{胡宇梦 \\ 信息与计算科学　3210103435}


\begin{document}
\maketitle

\section{简介}
（1）. 图的存储结构基于上一个项目中的Graph类


（2）. 实现了单源最短路径问题的Bellman-Ford算
法；输入：图（V,E）和起点original，输出：从ori
ginal到其他任意节点的最短路径（长度和最短路径构成）


（3）. Bellman-ford算法适用于单源最短路径，图中边的权
重可为负数即负权边，但不可以出现负权环

\section{设计思路}

（1）初始化 bak 和 dis 数组，将除第一个点外的所有顶点的最短路
径估计值赋值为 INF ， dis[1]=0。


（2）对输入的每条边反复进行松弛操作，使得 v1 到每个顶点的最
短路径估计值逐步逼近其最短路径，并用 check 来标记每轮松弛中数
组dis是否发生更新，直到数组 dis 不再发生变化，则说明 dis 数组中
已保存 v1 到各顶点的最短路径。


（3）输出最短路径所经顶点与相对应的最短路径值。

\section{测试说明}
（1）.输入错误检测
\begin{figure}[ht]
    \centering
    \includegraphics[width=5cm]{7.png}
    \caption{输入错误检测}
    \label{mode=1}
\end{figure}


（2）.功能测试。

数据如下：


\begin{figure}[ht]
    \centering
    \includegraphics[width=3cm]{1.jpg}
    \caption{测试数据1}
    \label{mode=1}
\end{figure} 
测试结果如下：
\begin{figure}[ht]
    \centering
    \includegraphics[width=6cm]{2.jpg}
    \caption{测试结果1}
    \label{mode=1}
\end{figure} 

由测试结果可知，此算法能够实现带有负权边的最短路径寻找。


（2）.算法效率测试。
Bellman-Ford理论算法复杂度为O(V*E)，用三组顶点数和
边数分别为:(20, 380)、（50，2450）、(100, 9900)的数据测
试该算法的效率，测
试数据由程序gen自动生成。三组测试数据输出分别为（由于数据太大，
截图截不完整，下面仅仅是部分截图）：


\begin{figure}[ht]
    \centering
    \includegraphics[width=7cm]{3.jpg}
    \caption{(20, 380)}
    \label{mode=1}
\end{figure} 

\begin{figure}[ht]
    \centering
    \includegraphics[width=7cm]{3.jpg}
    \caption{（50，2450）}
    \label{mode=1}
\end{figure} 

\begin{figure}[ht]
    \centering
    \includegraphics[width=7cm]{3.jpg}
    \caption{（100，9900）}
    \label{mode=1}
\end{figure} 


Bellman-Ford理论算法复杂度为O(V*E)，实验结果近似符合，验证成功！

\end{document}
